//
//  Problem1512.swift
//  TestProject
//
//  Created by 武侠 on 2021/4/7.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1512. 好数对的数目
 给你一个整数数组 nums 。

 如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
 返回好数对的数目。

 示例 1：
     输入：nums = [1,2,3,1,1,3]
     输出：4
     解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始
 示例 2：
     输入：nums = [1,1,1,1]
     输出：6
     解释：数组中的每组数字都是好数对
 示例 3：
     输入：nums = [1,2,3]
     输出：0
 提示：
     1 <= nums.length <= 100
     1 <= nums[i] <= 100
 */
@objcMembers class Problem1512: NSObject {
    func solution() {
        print(numIdenticalPairsAll([1,2,3,1,1,3]))
        print(numIdenticalPairsAll([1,1,1,1]))
        print(numIdenticalPairsAll([1,2,3]))
    }
    /*
     1: 创建一个字典：dic 记录每个值对于的下标数组，[1:[0, 3, 4], 2:[1], 3:[2, 5]]
     2: 使用公式：value.count * (value.count - 1) / 2
     
      [1]: 1 => 0 => 1 * (1 - 1) / 2
      [1 2]: 2 => 1 => 2 * (2 - 1) / 2
      [1 2 3] : 3 => 3 => 3 * (3 - 1) / 2
      [1 2 3 4] : 4 => 6 => 4 * (4 - 1) / 2
     */
    func numIdenticalPairs(_ nums: [Int]) -> Int {
        var dic:[Int:Int] = [:]
        for i in 0..<nums.count {
            dic[nums[i], default: 0] += 1
        }
        
        
        var result = 0
        for value in dic.values {
            result += value * (value - 1) / 2
        }
        return result
    }
    
    /*
     1: 创建一个数组list[100]: 1 <= nums[i] <= 100
     2: 遍历nums，把每个value放入输入list[value] += 1
     3: 遇到list[value]>2结果+1
     */
    func numIdenticalPairsAll(_ nums: [Int]) -> Int {
        var list = Array(repeating: 0, count: 100)      // 1 <= nums[i] <= 100
        var result = 0
        for value in nums {
            result += list[value]
            list[value] += 1
        }
        return result
    }
}
